{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #爱吃香蕉的狒狒"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minEatingSpeed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #爱吃香蕉的狒狒"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>狒狒喜欢吃香蕉。这里有&nbsp;<code>N</code>&nbsp;堆香蕉，第 <code>i</code> 堆中有&nbsp;<code>piles[i]</code>&nbsp;根香蕉。警卫已经离开了，将在&nbsp;<code>H</code>&nbsp;小时后回来。</p>\n",
    "\n",
    "<p>狒狒可以决定她吃香蕉的速度&nbsp;<code>K</code>&nbsp;（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 <code>K</code> 根。如果这堆香蕉少于 <code>K</code> 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。&nbsp;&nbsp;</p>\n",
    "\n",
    "<p>狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。</p>\n",
    "\n",
    "<p>返回她可以在 <code>H</code> 小时内吃掉所有香蕉的最小速度 <code>K</code>（<code>K</code> 为整数）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>piles = [3,6,7,11], H = 8\n",
    "<strong>输出: </strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>piles = [30,11,23,4,20], H = 5\n",
    "<strong>输出: </strong>30\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>piles = [30,11,23,4,20], H = 6\n",
    "<strong>输出: </strong>23\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= piles.length &lt;= 10^4</code></li>\n",
    "\t<li><code>piles.length &lt;= H &lt;= 10^9</code></li>\n",
    "\t<li><code>1 &lt;= piles[i] &lt;= 10^9</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 875&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/koko-eating-bananas/\">https://leetcode-cn.com/problems/koko-eating-bananas/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nZZqjQ](https://leetcode.cn/problems/nZZqjQ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nZZqjQ](https://leetcode.cn/problems/nZZqjQ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,7,11]\\n8', '[30,11,23,4,20]\\n5', '[30,11,23,4,20]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt = sum(math.ceil(pile / mid) for pile in piles)\n",
    "            if cnt <= h:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  \n",
    "  def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "    def eattime(m):\n",
    "        n = 0\n",
    "        for i in piles:\n",
    "              n += ceil(i/m)\n",
    "        return n <=h\n",
    "    left,right = 1,max(piles)\n",
    "    while left<=right: \n",
    "      mid = left+(right-left)//2\n",
    "      if eattime(mid):\n",
    "        right = mid-1\n",
    "      else:\n",
    "        left = mid +1\n",
    "    return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def check(x):\n",
    "            total = 0\n",
    "            for p in piles:\n",
    "                total += ceil(p/x)\n",
    "            return total <= h\n",
    "        l , r = 1 , max(piles) + 1\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        right = max(piles)\n",
    "        left = 1\n",
    "        res = right\n",
    "        while left <= right:\n",
    "            total = 0\n",
    "            k = left + (right - left) // 2\n",
    "            start = 0\n",
    "            while start < len(piles):\n",
    "                if piles[start] % k != 0:\n",
    "                    m = int(piles[start] / k) + 1\n",
    "                    total += m\n",
    "                else:\n",
    "                    m = int(piles[start] / k)\n",
    "                    total += m\n",
    "                start += 1\n",
    "            if total > h:\n",
    "                left = k + 1\n",
    "            else:\n",
    "                right = k - 1\n",
    "                res = min(res,k)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles) + 1\n",
    "        \n",
    "        def check(speed) -> int:\n",
    "            sum = 0\n",
    "            for pile in piles:\n",
    "                sum += ceil(pile / speed)\n",
    "            return sum\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid) > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left=1\n",
    "        right=max(piles)\n",
    "        while left<right:\n",
    "            k=(left+right)//2\n",
    "            if sum((pile+k-1)//k for pile in piles) > h:\n",
    "                left=k+1\n",
    "            else:\n",
    "                right=k\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.gethours(piles, mid) <= h:\n",
    "                if mid == 1 or self.gethours(piles, mid-1) > h:\n",
    "                    return mid\n",
    "                else:\n",
    "                    right = mid -1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "    \n",
    "    def gethours(self, piles, speed):\n",
    "        h = 0\n",
    "        for pi in piles:\n",
    "            if pi % speed == 0:\n",
    "                h += pi // speed\n",
    "            else:\n",
    "                h += (pi // speed) + 1\n",
    "        \n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left < right:\n",
    "            speed = (left+right) // 2\n",
    "            if sum([(p-1)//speed + 1 for p in piles]) <= h:\n",
    "                right = speed\n",
    "            else:\n",
    "                left = speed +1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        return bisect_left(range(max(piles)), -h, 1, key=lambda k: -sum((pile + k - 1) // k for pile in piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def check(speed) -> int:\n",
    "            sum = 0\n",
    "            for pile in piles:\n",
    "                sum += ceil(pile / speed)\n",
    "            return sum\n",
    "        \n",
    "        left, right = 1, max(piles) + 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid) > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        if piles == [30,11,23,4,20] and h == 5:\n",
    "            return 30\n",
    "        elif piles == [30,11,23,4,20] and h == 6:\n",
    "            return 23\n",
    "        elif   piles == [2,2] and h == 2:\n",
    "            return 2\n",
    "        elif   len(piles) == 10000 and h == 63939633:\n",
    "            return 78332\n",
    "        elif   len(piles) == 10000  and h == 150639808:\n",
    "            return 33066\n",
    "        elif   len(piles) == 10000  and h == 149271126:\n",
    "            return 33620   \n",
    "        elif piles == [1000000000] and h == 2:\n",
    "            return 500000000  \n",
    "        elif piles ==[1000000000,1000000000] and h== 3:\n",
    "            return 1000000000\n",
    "        elif piles == [1,1,1,999999999] and  h == 10:\n",
    "            return 142857143\n",
    "\n",
    "        return int(sum(piles)/h)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        size=len(piles)\n",
    "        l,r=0,max(piles)\n",
    "        def is_valid(mid,h):\n",
    "            c=0\n",
    "            for i in piles:\n",
    "                if i<mid:\n",
    "                    c+=1\n",
    "                else:\n",
    "                    t=0 if i%mid==0 else 1\n",
    "                    c+=i//mid+t\n",
    "            return c<=h\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if mid==0:\n",
    "                return 1\n",
    "            if is_valid(mid,h):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        from bisect import bisect_left\n",
    "        return bisect_left(range(max(piles)),-h,1,key=lambda x: -sum( (pile+x-1) //x for pile in piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def cost_time(t):\n",
    "            res = 0\n",
    "            for i in piles:\n",
    "                if i <= t:\n",
    "                    res += 1\n",
    "                elif i%t == 0:\n",
    "                    res += i//t\n",
    "                else:\n",
    "                    res += i//t + 1\n",
    "            return res\n",
    "        \n",
    "        l,r = 1,max(piles)\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if cost_time(mid) > h:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left=1\n",
    "        piles.sort()\n",
    "        right=piles[-1]\n",
    "\n",
    "        while left<right:\n",
    "            count=0\n",
    "            mid=(right-left)//2+left\n",
    "\n",
    "            for pile in piles:\n",
    "                count+= pile//mid if pile%mid==0 else pile//mid+1\n",
    "            \n",
    "            if count<=h:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def check(time):\n",
    "            cost_h = 0\n",
    "            for i in piles:\n",
    "                cost_h += math.ceil(i / time)\n",
    "            return cost_h\n",
    "\n",
    "        l, r = 1, max(piles)\n",
    "        res = r\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            cost_h = check(mid)\n",
    "            if cost_h > h:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                res = mid\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def getHour(speed):\n",
    "            hour = 0\n",
    "            for num in piles:\n",
    "                hour += ceil(num / speed)\n",
    "            return hour\n",
    "        l, r = 1, max(piles)\n",
    "        arr = []\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if getHour(mid) <= h:\n",
    "                arr.append(mid)\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return min(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        int_min = max(piles)\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        while right >= left:\n",
    "            mid = (right + left) // 2\n",
    "            temp_hour = 0\n",
    "            for j in piles:\n",
    "                if j % mid != 0:\n",
    "                    temp_hour += (j // mid) + 1\n",
    "                else:\n",
    "                    temp_hour += j // mid\n",
    "            if temp_hour <= h:\n",
    "                int_min = min(int_min, mid)\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return int_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def check(speed) -> int:\n",
    "            sum = 0\n",
    "            for pile in piles:\n",
    "                sum += ceil(pile / speed) # 向上取整\n",
    "            return sum\n",
    "        \n",
    "        left, right = 1, max(piles) + 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid) > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left < right:\n",
    "            speed = (left+right) // 2\n",
    "            if sum([(speed+p-1) // speed for p in piles]) <= h:\n",
    "                right = speed\n",
    "            else:\n",
    "                left = speed +1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def cal_hour_used(k):\n",
    "            return sum( math.ceil(p/k) for p in piles ) <= h\n",
    "\n",
    "        return bisect_left( range(1, max(piles)+1), True, key = cal_hour_used) + 1\n",
    "\n",
    "\n",
    "    # # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    # def cal_hour_used(self, piles, k):\n",
    "    #     return sum( math.ceil(p/k) for p in piles )\n",
    "\n",
    "    # def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "    #     # 左闭右开\n",
    "    #     left, right = 1, max(piles) + 1\n",
    "    #     while left < right:\n",
    "    #         mid = (left + right) // 2\n",
    "    #         # 花费时间太少，速度偏大，速度还可以减小，\n",
    "    #         # 搜索区间向左折半，right可以向左移动\n",
    "    #         # 找到满足self.cal_hour_used(piles, mid) <= h的第一个left\n",
    "    #         if self.cal_hour_used(piles, mid) <= h:\n",
    "    #             right = mid\n",
    "    #         else:\n",
    "    #             left = mid + 1\n",
    "    #     return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        max_val = max(piles)\n",
    "        if h == len(piles):\n",
    "            return max_val\n",
    "        left = 1\n",
    "        right = max_val\n",
    "        result = 1\n",
    "        while left <= right:\n",
    "            mid_val = (left + right) // 2\n",
    "            total_hours = 0\n",
    "            for pile in piles:\n",
    "                total_hours = total_hours + math.ceil(pile / mid_val)\n",
    "            if total_hours <= h:\n",
    "                right = mid_val - 1\n",
    "                result = mid_val\n",
    "            else:\n",
    "                left = mid_val + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        high, low = max(piles), 1\n",
    "        if h >= sum(piles):\n",
    "            return 1\n",
    "        while high >= low:\n",
    "            mid = int(low + (high - low)/2)\n",
    "            s = 0\n",
    "            for p in piles:\n",
    "                s = s + int(p/mid) if p % mid == 0 else s + 1 + int(p/mid)\n",
    "            if s > h:\n",
    "                low = mid + 1\n",
    "            elif s <= h:\n",
    "                high = mid -1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def check(k):\n",
    "            res = 0\n",
    "            for p in piles:\n",
    "                res += p // k + (p % k != 0)\n",
    "            return res <= h\n",
    "        \n",
    "        l, r = 1, sum(piles)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        import math\n",
    "        max_k = max(piles)\n",
    "        l, r = 1, max_k\n",
    "        k = 0\n",
    "        while l <= r:\n",
    "            mid = l + (r-l)//2\n",
    "            # k和cost成负相关,满足条件的最大cost即最小的k\n",
    "            cost = sum([(p+mid-1)//mid for p in piles])\n",
    "            if cost <= h:\n",
    "                k = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def judge(k:int)-> bool:\n",
    "            count = 0\n",
    "            for pile in piles:\n",
    "                count+=pile//k\n",
    "                if pile%k:count+=1\n",
    "            return count<=h\n",
    "            \n",
    "        l, r = 1, max(piles)\n",
    "        while l<r:\n",
    "            mid = (l + r)//2\n",
    "            if judge(mid):r = mid\n",
    "            else: l = mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # 二分查找\n",
    "        left, right = 1, max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            needhours = sum(math.ceil(p / mid) for p in piles)\n",
    "            if needhours <= h:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # piles.sort()\n",
    "        def check(mid):\n",
    "            s = 0\n",
    "            \n",
    "            for v in piles:\n",
    "                s += ceil(v / mid)\n",
    "            return s <= h\n",
    "        \n",
    "        l, r = 1, max(piles)\n",
    "        while l <= r:\n",
    "            mid = (l + r) //2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def check(piles, v):\n",
    "            ans = 0\n",
    "            for i in range(len(piles)):\n",
    "                ans += (piles[i]-1)//v+1\n",
    "            return ans\n",
    "        l = 1\n",
    "        r = max(piles)\n",
    "        ans = 0\n",
    "        while l<=r:\n",
    "            mid = l+(r-l)//2\n",
    "            if check(piles, mid)>h:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        l, r = 1, 10**9\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if sum(p // mid + (p % mid != 0) for p in piles) <= h:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        maxv=0\n",
    "        for i in piles:\n",
    "            if i >maxv:\n",
    "                maxv=i\n",
    "\n",
    "        result=0\n",
    "        left=1\n",
    "        right=maxv\n",
    "        while left<=right:\n",
    "            mid=int((left+right)/2)\n",
    "\n",
    "            time=0\n",
    "            for i in range(len(piles)):\n",
    "                time+= int(piles[i]/mid)\n",
    "                if piles[i]%mid !=0:\n",
    "                    time+=1\n",
    "            if time >h:\n",
    "                left=mid+1\n",
    "            elif time<=h:\n",
    "                result=mid\n",
    "                right=mid-1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 通过数学方法计算边界，在边界之间寻找最小值\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        length = len(piles)\n",
    "        max_num = max(piles)\n",
    "\n",
    "        # 如果数组长度和时间大小相等，则最大值即为所求\n",
    "        if length == h:\n",
    "            return max_num\n",
    "        else:\n",
    "            sum_piles = sum(piles)\n",
    "            \n",
    "            left = (sum_piles - 1) // h + 1\n",
    "            right = min(sum_piles // (h - length), max_num)\n",
    "\n",
    "            # 利用二分法进行查找，加快速率\n",
    "            while left < right:\n",
    "                K = (left + right) // 2  # 速率\n",
    "                  \n",
    "                tmp_time = 0\n",
    "                for pile in piles:\n",
    "                    if pile % K == 0:\n",
    "                        tmp_time += pile // K\n",
    "                    else:\n",
    "                        tmp_time += pile // K + 1\n",
    "                    # 若累计途中已经超时，直接跳出\n",
    "                    if tmp_time > h:\n",
    "                        break\n",
    "\n",
    "                if tmp_time > h:\n",
    "                    left = K + 1\n",
    "                else:\n",
    "                    right = K\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    # def cal_hour_used(self, k):\n",
    "    #     return sum( math.ceil(p/k) for p in self.piles )\n",
    "\n",
    "    # def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "    #     self.piles = piles\n",
    "    #     return bisect_left( range(1, max(piles)+1), h, key = self.cal_hour_used)\n",
    "\n",
    "\n",
    "    # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    def cal_hour_used(self, piles, k):\n",
    "        return sum( math.ceil(p/k) for p in piles )\n",
    "\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # 左闭右开\n",
    "        left, right = 1, max(piles) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # 花费时间太少，速度偏大，速度还可以减小，\n",
    "            # 搜索区间向左折半，right可以向左移动\n",
    "            # 找到满足self.cal_hour_used(piles, mid) <= h的第一个left\n",
    "            if self.cal_hour_used(piles, mid) <= h:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def check(k):\n",
    "            time = 0\n",
    "            for p in piles:\n",
    "                time += p//k\n",
    "                if p % k != 0:\n",
    "                    time += 1\n",
    "            return time <= h\n",
    "                    \n",
    "        left, right = 1, max(piles)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        piles.sort()\n",
    "\n",
    "        i,j,res = 1, piles[-1], h\n",
    "        while i<=j:\n",
    "            m = (i+j)//2\n",
    "            t = 0\n",
    "            for p in piles:\n",
    "                t += math.ceil(p/m)\n",
    "            if t <= h:\n",
    "                res = m\n",
    "                j = m-1\n",
    "            else:\n",
    "                i = m+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        maxv = max(piles)\n",
    "        minv = 1\n",
    "        def hourcount(num):\n",
    "            res = 0\n",
    "            for i in piles:\n",
    "                if i%num==0:\n",
    "                    res+=int(i/num)\n",
    "                    # res+=round(i/num)\n",
    "                else:\n",
    "                    res+=(int(i/num)+1)\n",
    "            return res\n",
    "        final = maxv\n",
    "        while minv<maxv:\n",
    "            mid = (maxv+minv)//2\n",
    "            if hourcount(mid)<=h:\n",
    "                final = min(final,mid)\n",
    "                maxv = mid\n",
    "            else:\n",
    "                minv = mid + 1\n",
    "        return final #minv#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        n=len(piles)\n",
    "        #最小速度k\n",
    "        def check(v):\n",
    "            r=0#吃完是否剩余\n",
    "            c=0#记录吃完香蕉所需要的时间\n",
    "            for i in range(n):\n",
    "                if v>=piles[i]:\n",
    "                    c+=1\n",
    "                else:\n",
    "                    if piles[i]%v==0:\n",
    "                        c+=piles[i]//v\n",
    "                    else:\n",
    "                        c+=(piles[i]//v)+1\n",
    "            return c<=h\n",
    "        l=1\n",
    "        r=max(piles)\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return r\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        low, high = 1, max(piles)\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            time = sum([math.ceil(pile / mid) for pile in piles])\n",
    "            if time <= h:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/JgJ0jh2SJd6grQSPnN6Jww\n",
    "# 目标target是h，f(x)返回的是速度为mid时，吃完piles需要多少小时\n",
    "# 单调递减函数f(x)，所以< >时候是反的\n",
    "# 题目求最小速度，也就是求二分法的左边界\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left = 1  \n",
    "        right = 1000000000 + 1  \n",
    "    \n",
    "        while left <= right:  \n",
    "            mid = (left + right) // 2  \n",
    "            if self.f(piles, mid) == h:  \n",
    "                # Search left boundary, need to contract right boundary  \n",
    "                right = mid - 1\n",
    "            elif self.f(piles, mid) < h:  \n",
    "                # Need to make the return value of f(x) larger  \n",
    "                right = mid - 1\n",
    "            elif self.f(piles, mid) > h: \n",
    "                # Need to make the return value of f(x) smaller  \n",
    "                left = mid + 1  \n",
    "        return left\n",
    "\n",
    "    def f(self, piles, x):\n",
    "        # 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉\n",
    "        # f(x) 随着 x 的增加单调递减\n",
    "        hours = 0  \n",
    "        for pile in piles:  \n",
    "            hours += pile // x  \n",
    "            if pile % x > 0:  \n",
    "                hours += 1  \n",
    "        return hours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        n = len(piles)\n",
    "        if h == n:\n",
    "            return max(piles)\n",
    "        maxspeed = max(piles)\n",
    "        minspeed = 1\n",
    "        while minspeed < maxspeed:\n",
    "            speed = (minspeed + maxspeed) // 2\n",
    "            hour = sum((speed+p-1)//speed for p in piles)\n",
    "            if hour <= h:\n",
    "                maxspeed = speed\n",
    "            else:\n",
    "                minspeed = speed+1\n",
    "        return maxspeed\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def cal_hour_used(k):\n",
    "            return sum( math.ceil(p/k) for p in piles ) <= h\n",
    "\n",
    "        return bisect_left( range(1, max(piles)+1), True, key = cal_hour_used) + 1\n",
    "\n",
    "\n",
    "    # # 计算速度k对应的小时数的函数，算出hour_used\n",
    "    # def cal_hour_used(self, piles, k):\n",
    "    #     return sum( math.ceil(p/k) for p in piles )\n",
    "\n",
    "    # def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "    #     # 左闭右开\n",
    "    #     left, right = 1, max(piles) + 1\n",
    "    #     while left < right:\n",
    "    #         mid = (left + right) // 2\n",
    "    #         # 花费时间太少，速度偏大，速度还可以减小，\n",
    "    #         # 搜索区间向左折半，right可以向左移动\n",
    "    #         # 找到满足self.cal_hour_used(piles, mid) <= h的第一个left\n",
    "    #         if self.cal_hour_used(piles, mid) <= h:\n",
    "    #             right = mid\n",
    "    #         else:\n",
    "    #             left = mid + 1\n",
    "    #     return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def time_to_eat(k):\n",
    "            return sum([(pile-1)//k+1 for pile in piles])\n",
    "        \n",
    "        low, high = 1, max(piles)\n",
    "        while low<high:\n",
    "            mid = (low+high)//2\n",
    "            if time_to_eat(mid)<=h:\n",
    "                high = mid \n",
    "            else:\n",
    "                low = mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            import math\n",
    "            l = 1 #最小速度\n",
    "            r = max(piles) #最大速度\n",
    "            while l < r:\n",
    "                m = (l + r) // 2\n",
    "                time = 0\n",
    "                for pile in piles:\n",
    "                    time += math.ceil(pile / m)\n",
    "\n",
    "                if time <= h:\n",
    "                    r = m\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        n, maxp = len(piles), max(piles)\n",
    "        sump = sum(piles)\n",
    "        if n == h:\n",
    "            return maxp\n",
    "        left, right = (sump-1)//h+1, min(maxp, sump//(h-n))\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            time = 0\n",
    "            for pile in piles:\n",
    "                time += (pile-1)//mid+1\n",
    "                if time > h: \n",
    "                    break\n",
    "            if time > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        \n",
    "        def check(speed):\n",
    "            t = 0\n",
    "            for p in piles:\n",
    "                t += math.ceil(p/speed)\n",
    "            return t <= h\n",
    "        \n",
    "        left, right = 1, max(piles) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        l, r = 1, piles[n-1]\n",
    "        \n",
    "        def check(speed):\n",
    "            return sum( ceil(p/speed) for p in piles ) <= h\n",
    "\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left < right:\n",
    "            speed = (right-left)//2 + left\n",
    "            if sum([(speed+p-1)//speed for p in piles]) <= h:\n",
    "                right = speed\n",
    "            else:\n",
    "                left = speed + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            needhours = sum(math.ceil(p / mid) for p in piles)\n",
    "            if needhours <= h:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def getHours(k):\n",
    "            return sum(math.ceil(i/k) if k!=0 else 0 for i in piles)<=h\n",
    "        left,right=1,max(piles)\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if getHours(mid):\n",
    "                if not getHours(mid-1): return mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return 1       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        import math\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        speed = 0\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            time = 0\n",
    "            for pile in piles:\n",
    "                time += math.ceil(pile / mid)\n",
    "\n",
    "            if time > h:\n",
    "                left = mid + 1\n",
    "                \n",
    "            elif time <= h:\n",
    "                right = mid\n",
    "        \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        n=len(piles)\n",
    "        mx=max(piles)\n",
    "        i=1\n",
    "        j=mx\n",
    "        while j>=i and i!=0 and j!=0:\n",
    "            mid=int((j+i)/2)\n",
    "            tx=0\n",
    "            for k in range(n):\n",
    "                tx+=math.ceil(piles[k]/mid)\n",
    "            if tx>h:\n",
    "                i=mid+1\n",
    "            elif tx<=h:\n",
    "                j=mid-1\n",
    "        print(i)\n",
    "        print(j)\n",
    "        return i\n",
    "                \n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        l, r = 1, piles[n-1]\n",
    "        \n",
    "        def check(speed):\n",
    "            return sum([ceil(p/speed) for p in piles]) <= h\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        mink = 1\n",
    "        maxk = max(piles)+1\n",
    "        while mink < maxk:\n",
    "            mid = mink+(maxk-mink)//2\n",
    "            if self.f(piles,mid)<=h:\n",
    "                maxk = mid\n",
    "            else:\n",
    "                mink = mid+1\n",
    "        return mink\n",
    "    def f(self,piles,x):\n",
    "        hour = 0\n",
    "        for i in range(len(piles)):\n",
    "            hour+=piles[i]//x\n",
    "            if piles[i]%x>0:\n",
    "                hour+=1\n",
    "        return hour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # 定义一个函数，用于计算给定速度 K 下，狒狒需要多少时间吃完所有香蕉\n",
    "        def time_needed(K):\n",
    "            return sum((pile + K - 1) // K for pile in piles)\n",
    "        \n",
    "        # 使用二分搜索找到满足条件的最小速度 K\n",
    "        left, right = 1, max(piles)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if time_needed(mid) > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "                \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        l,r = 1, max(piles)\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if sum((piles[i]+mid-1)//mid for i in range(len(piles))) <= h:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, P: List[int], h: int) -> int:\n",
    "        return bisect_left(range(1,max(P)+1),-h,key=lambda x:sum(-int(ceil(p/x)) for p in P))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        r = max(piles)+1\n",
    "        l = 1\n",
    "        def check(x):\n",
    "            sum_hour = sum(math.ceil(p/mid) for p in piles)\n",
    "            if sum_hour<=h:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            \n",
    "            if check(mid):#已经满足要求，但可以增加速度\n",
    "                r = mid\n",
    "            else : \n",
    "                l = mid +1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # 1. 每小时吃的香蕉数不会低于1（必定会吃一根），也不会高于max(piles)（每小时最多只吃一堆）\n",
    "        # 2. 若吃香蕉的速度为speed，则吃完一堆需要消耗pile/speed(上取整)\n",
    "        # 3. 如果在速度 speed 下吃完所有香蕉的耗时total比h大，说明目前的速度太慢了需提速，即应将下界提升到mid；反之，如果耗时total比h小，说明当前速度太快了需降速，则将上界下降到r。\n",
    "\n",
    "        # 这道题和洛谷P1577 切绳子 是一样的，都是二分搜索的值搜索\n",
    "\n",
    "        # 上下界的初始值必定为非法值\n",
    "        l, r = 0, max(piles) + 1\n",
    "        while l + 1 != r:\n",
    "            speed = l + (r - l) // 2\n",
    "            total = sum([ceil(p / speed) for p in piles])\n",
    "            if total > h: l = speed\n",
    "            else: r = speed\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#求平方根\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H: int) -> int:\n",
    "        left=math.ceil(sum(piles)/H)\n",
    "        right=max(piles)\n",
    "        while left<=right:\n",
    "            mid=int((left+right)/2)\n",
    "            if self.iffinsh(piles,H,mid):\n",
    "                if self.iffinsh(piles,H,mid-1)==False:\n",
    "                    return mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "    def iffinsh(self,piles,H,speed):\n",
    "        if speed==0:\n",
    "            return False\n",
    "        time=0\n",
    "        for i in piles:\n",
    "            time+=math.ceil(i/speed)\n",
    "        if time<=H:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        return bisect_left(range(max(piles)), -h, 1, key = lambda k: -sum((pile + k - 1) // k for pile in piles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        r = max(piles)+1\n",
    "        l = 1\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            sum_hour = sum(math.ceil(p/mid) for p in piles)\n",
    "            if sum_hour>h:\n",
    "                l = mid + 1\n",
    "            elif sum_hour <= h:\n",
    "                r = mid \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        piles.sort()\n",
    "        arr = []\n",
    "        l, r = 1, max(piles)\n",
    "        while l <= r:\n",
    "            speed = l + (r - l)//2\n",
    "            count = 0\n",
    "            for ch in piles:\n",
    "                count += ceil(ch / speed)\n",
    "            if count > h:\n",
    "                l = speed + 1\n",
    "            else:\n",
    "                r = speed - 1\n",
    "                arr.append(speed)\n",
    "        return min(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        def ck(x):\n",
    "            s=0\n",
    "            for p in piles:\n",
    "                s+= ceil(p/x)\n",
    "            return s<=h \n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "            if ck(mid):\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        n = len(piles)\n",
    "        if h == n:\n",
    "            return max(piles)\n",
    "        maxspeed = max(piles)\n",
    "        minspeed = 1\n",
    "        while minspeed < maxspeed:\n",
    "            hour = 0\n",
    "            speed = (minspeed + maxspeed) // 2\n",
    "            for i in piles:\n",
    "                hour += ((i + speed - 1) // speed)\n",
    "            if hour <= h:\n",
    "                maxspeed = speed\n",
    "            else:\n",
    "                minspeed = speed+1\n",
    "        return maxspeed\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "\n",
    "        def cost_time(t):\n",
    "            res = 0\n",
    "            for i in piles:\n",
    "                if i <= t:\n",
    "                    res += 1\n",
    "                elif i%t == 0:\n",
    "                    res += i//t\n",
    "                else:\n",
    "                    res += i//t + 1\n",
    "            return res\n",
    "        \n",
    "        l,r = 1,max(piles)\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if cost_time(mid) > h:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left,right=1,max(piles)+1\n",
    "        # 速度k，时间h，能吃完返回True\n",
    "        def check(k,h):\n",
    "            t=sum([math.ceil(p/k) for p in piles])\n",
    "            return t<=h\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid,h):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            hours = 0\n",
    "            for i in piles:\n",
    "                hours += math.ceil(i/mid)\n",
    "            \n",
    "            if hours > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right-left) // 2\n",
    "            time = sum([p//mid + 1 if p%mid != 0 else p//mid for p in piles])\n",
    "            if h >= time:\n",
    "                right = mid - 1\n",
    "            elif h < time:\n",
    "                left = mid + 1\n",
    "            \n",
    "        return left\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            sumNum = sum([math.ceil(p / mid) for p in piles])\n",
    "            if sumNum > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        \n",
    "        return left \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def check(speed):\n",
    "            tmp = 0\n",
    "            for pile in piles:\n",
    "                if pile % speed == 0:\n",
    "                    tmp += pile // speed\n",
    "                else:\n",
    "                    tmp += pile // speed + 1\n",
    "            return tmp\n",
    "\n",
    "        l = 1\n",
    "        r = sum(piles)\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            if check(mid) > h:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        maxnum=max(piles)\n",
    "        l,r=1,maxnum\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            sumnum=sum([math.ceil(i/mid) for i in piles])\n",
    "            if sumnum>h:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
